Path with maximum gold

Time: O(M2xN2); Space: O(MxN); medium

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions: * Every time you are located in a cell you will collect all the gold in that cell. * From your position you can walk one step to the left, right, up or down. * You can’t visit the same cell more than once. * Never visit a cell with 0 gold. * You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]

Output: 24

Explanation:

[[0,6,0],
 [5,8,7],
 [0,9,0]]

Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

Output: 28

Explanation:

[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]

Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints:

  • 1 <= len(grid), len(grid[i]) <= 15

  • 0 <= grid[i][j] <= 100

  • There are at most 25 cells containing gold.

Hints:

  1. Use recursion to try all such paths and find the one with the maximum value.

[1]:

class Solution1(object):
    """
    Time: O(M^2*N^2)
    Space: O(M*N)
    """
    def getMaximumGold(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        def backtracking(grid, i, j):
            result = 0
            grid[i][j] *= -1
            for dx, dy in directions:
                ni, nj = i+dx, j+dy
                if not (0 <= ni < len(grid) and
                        0 <= nj < len(grid[0]) and
                        grid[ni][nj] > 0):
                    continue
                result = max(result, backtracking(grid, ni, nj))
            grid[i][j] *= -1
            return grid[i][j] + result

        result = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]:
                    result = max(result, backtracking(grid, i, j))
        return result

[3]:

s = Solution1()

grid = [[0,6,0],[5,8,7],[0,9,0]]
assert s.getMaximumGold(grid) == 24

grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
assert s.getMaximumGold(grid) == 28